package com.jay.mypracticesdemo

import org.junit.Before
import org.junit.Test
import java.util.LinkedList
import java.util.Queue
import java.util.Stack


class TestTreeNode {

    class TreeNode() {
        var value: Int? = null
        var left: TreeNode? = null
        var right: TreeNode? = null

        constructor(v: Int) : this() {
            value = v
        }
    }

    /**
     *       1
     *     /   \
     *  2         3
     *          /  \
     *         4    5
     *       /  \
     *      9    6
     *      \    / \
     *      10   7  8
     *       \
     *       11
     */
    fun fillNode(): TreeNode {
//        val array = arrayOf(1, 2, 3, 4, 5)

        val root = TreeNode(1)
        val left2 = TreeNode(2)
        val right2 = TreeNode(3)
        root.left = left2
        root.right = right2
        right2.left = TreeNode(4)
        right2.right = TreeNode(5)
        right2.left!!.right = TreeNode(6)
        right2.left!!.right!!.left = TreeNode(7)
        right2.left!!.right!!.right = TreeNode(8)
        right2.left!!.left = TreeNode(9)
        right2.left!!.left!!.right = TreeNode(10)
        right2.left!!.left!!.right!!.right = TreeNode(11)
        return root
    }

    var fillNode: TreeNode? = null

    @Before
    fun setUp() {
        fillNode = fillNode()
    }


    @Test
    fun testLevelOrderRecurve() {
        fun levelOrder(node: TreeNode?, level: Int, levelList: ArrayList<ArrayList<Int?>>, direction: String) {
            if (node == null) return

            println("level:${level + 1} $direction")
            if (levelList.size == level) {
                levelList.add(ArrayList())
            }

            node.value?.let {
                levelList[level].add(it)
            }

            levelOrder(node.left, level + 1, levelList, "left")
            levelOrder(node.right, level + 1, levelList, "right")
        }

        val arrayListOf: ArrayList<ArrayList<Int?>> = arrayListOf()
        levelOrder(fillNode!!, 0, arrayListOf, "root")
        arrayListOf.forEach { item ->
            val reduce = item.map { return@map "$it" }.reduce(reduceCallback())
            println("可以[$reduce]")
        }
        val s1 = arrayListOf.map { list->
            "这$list" }.reduce { acc, s -> "$acc $s" }
        println(s1)

        fun bfsPrintLevels(root: TreeNode?): List<List<Int>> {
            val result: MutableList<List<Int>> = java.util.ArrayList()
            if (root == null) {
                return result
            }
            val queue: Queue<TreeNode> = LinkedList()
            queue.add(root)
            while (!queue.isEmpty()) {
                val size = queue.size
                val levelList: MutableList<Int> = java.util.ArrayList()
                for (i in 0 until size) {
                    val node = queue.poll()
                    levelList.add(node.value!!)
                    if (node.left != null) {
                        queue.add(node.left)
                    }
                    if (node.right != null) {
                        queue.add(node.right)
                    }
                }
                result.add(levelList)
            }
            return result
        }
        //非递归方式
        /**
         * 队列和迭代去层级遍历二叉树，但是没有保存住每一层的节点缓存数组，非递归的方式遍历的。
         */
        fun levelOrderNonRecursive(quee: LinkedList<TreeNode>) {
            val arrayListOf2: ArrayList<ArrayList<String>> = arrayListOf()
            while (quee.isNotEmpty()) {
                val listOf2 = arrayListOf<String>()
                val size = quee.size
                println("for size=$size")
                for (i in 0 until size) {
                    println("i=$i ${quee.size}")
                    val node = quee.poll()
                    println(" after i=$i ${quee.size}")

                    node?.value?.let {
                        listOf2.add("$it")
                    }
                    node?.left?.let { quee.add(it) }
                    node?.right?.let { quee.add(it) }
                    println(" after add i=$i ${quee.size}")

                }
                arrayListOf2.add(listOf2)
            }
            arrayListOf2.forEach { item ->
                val reduce = item.takeIf { it.isNotEmpty() }?.map { return@map "$it" }?.reduce(reduceCallback())
                println(" 好[$reduce]")
            }
            val s2 = arrayListOf2.map { "$it" }.reduce { acc, s -> "$acc $s" }
            println("非递归的广度：$s2")
        }

        val quee: LinkedList<TreeNode> = LinkedList<TreeNode>().apply {
            add(0, fillNode!!)
        }
        levelOrderNonRecursive(quee);
    }

    @Test
    fun testInOrderRecurve() {
        val arrayListOf = arrayListOf<Any?>()
        fun inOrder(node: TreeNode?, level: Int, direction: String) {
            println("level:${level + 1} $direction")

            if (node == null) return

            inOrder(node.left, level + 1, "left")
            //中序根
            println("root=${node.value}")
            arrayListOf.add(node.value)
            inOrder(node.right, level + 1, "right")
        }

        inOrder(fillNode!!, 0, "root")
        val reduce = arrayListOf.map { "$it" }.reduce { acc, s -> "$acc $s" }
        println("size=${arrayListOf.size}: [$reduce]")
    }

    @Test
    fun testPostOrderRecurve() {
        val arrayListOf = arrayListOf<Any?>()
        fun postOrder(node: TreeNode?, level: Int, direction: String) {
            println("level:${level + 1} $direction")

            if (node == null) return//空左子树、空右子树时结束当前左子树递归、结束当前右子树递归，为方法栈弹回上一个节点 根读取值

            postOrder(node.left, level + 1, "left")//左子树
            postOrder(node.right, level + 1, "right")//右子树
            //后序根
            println("root=${node.value}")
            arrayListOf.add(node.value)
        }

        postOrder(fillNode!!, 0, "root")
        val reduce = arrayListOf.map { "$it" }.reduce { acc, s -> "$acc $s" }
        println("size=${arrayListOf.size}: [$reduce]")


        fun postOrderNonRecursive() {
            val stack = Stack<TreeNode>()
            val outStack = Stack<Int>()
            stack.push(fillNode)
            while (stack.isNotEmpty()) {
                val pop = stack.pop()
                outStack.push(pop.value)

                pop.right?.let { stack.push(it) }
                pop.left?.let { stack.push(it) }
            }

            val arrayListOf1 = arrayListOf<Any?>()
            while (outStack.isNotEmpty()) {
                val pop = outStack.pop()
                arrayListOf1.add(pop)
            }
            val reduce2 = arrayListOf1.map { "$it" }.reduce { acc, s -> "$acc $s" }
            println("size=${arrayListOf1.size}: [$reduce2]")
        }

        postOrderNonRecursive()
    }

    private fun reduceCallback(): (acc: String, String) -> String = { acc, s -> "$acc $s" }

}